// 子串哈希
// https://www.luogu.com.cn/problem/P4421

const int base = 26;
const ll mod = 0x003f003f003f003fLL;
int decoder[128];
ll po[max_size];

void init_decoder() {
    po[0] = 1;
    for (int i = 1; i < max_size; ++i)
        po[i] = po[i - 1] * base;
    for (int i = 1; i <= 26; ++i)
        decoder['a' + i - 1] = i;
}

char row[max_size];
ll pre[max_size];

void init_pre() {
    int len = strlen(row + 1);
    for (int i = 1; i <= len; ++i) {
        pre[i] = (pre[i - 1] * base + decoder[row[i]]) % mod;
    }
}

ll ask(int l, int r) {
    return (pre[r] - pre[l - 1] * po[r - l + 1] + 128 * mod) % mod;
}
